In recent years, Internet Service Providers (ISPs) have been rolling out a wide range of value added services beyond basic connectivity, such as web hosting, content distribution network (CDN) services, database services, gaming services, cloud computing, e-commerce server hosting, etc. In many cases, customers access these value added services via an Internet connection and, as such, customers can be dispersed over a wide geographic area. Additionally, the value added services provided by an ISP are often hosted in geographically distributed data centers, which may be co-located with an ISP's different Points of Presence (PoPs). Detecting and localizing end-to-end performance issues for such wide-area services can be useful to an ISP operator for achieving desired end user service quality, such as by enabling fast service impairment detection and flexible mitigation control. Existing techniques for detecting and localizing performance issues and other network anomalies can involve using active probes placed strategically in an ISP's wide-area network that inject probe packets into the network to enable detection of anomalies associated with the locations of the active probes.